package dp.路径;

import java.util.List;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 三角形最小路径和120.java
 * @createTime 2024年03月05日 17:55:00
 */
public class 三角形最小路径和120 {
	/*
   把    [2],
	   [3,4],
	  [6,5,7],
	 [4,1,8,3]
	变形为
   [2],
   [3,4],
   [6,5,7],
   [4,1,8,3]

   重复子问题
   状态：选择节点的位置
   选择：i或者i+1
   定义函数dp[i][j]表示在第i行位置j有最最小的路径和dp[i][j]
   dp[i][j]=min(dp[i-1][j],dp[i-1][j])+num[i][j]
   basecase:
   dp[0]=triangle.get(0).get(0);
   边界情况：
   1. 列表为null，为空集合
   2. j=0的情况，只能从扇面下来 dp[i][0]=dp[i-1][j]+triangle.get(i).get(j);
   3. j=triangle[i].length也就是j=i的情况，只能从最上面下来 dp[i][triangle[i].length-1]=dp[i-1][j-1]+triangle.get(i).get(j);
	*/
	public int minimumTotal(List<List<Integer>> triangle) {
		if (triangle == null || triangle.size() == 0) {
			return 0;
		}
		int row = triangle.size();
		int col = triangle.get(row - 1).size();
		int[][] dp = new int[row][col];
		dp[0][0] = triangle.get(0).get(0);
		int min = Integer.MAX_VALUE;
		for (int i = 1; i < row; i++) {
			for (int j = 0; j <= i; j++) {
				if (j == 0) {
					dp[i][j] = dp[i - 1][j] + triangle.get(i).get(j);
				} else if (j == i) {
					dp[i][j] = dp[i - 1][j - 1] + triangle.get(i).get(j);
				} else {
					dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j-1]) + triangle.get(i).get(j);
				}
			}
		}
		for (int i : dp[row - 1]) {
			min = Math.min(i, min);
		}
		return min;
	}
}
